class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // map<char,int> mm;
        int ret = 0;
        int left = 0,right = 0;
        unordered_set<char> ss;
        for(;right < s.size();right++){
            while(ss.count(s[right])) // ss 里有right
            {
                ss.erase(s[left++]);
            }
            ss.insert(s[right]);
            ret =  max(ret,right - left + 1);
        }
        return ret;
    }
};
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        nums.insert(nums.begin(),0);
        nums.insert(nums.end(),0);
        vector<int> left(nums.size()),right(nums.size());
        int size = nums.size();
        left[0] = nums[0];
        for(int i = 1;i < size;i++){
            left[i] = nums[i] == 0 ? 0 : left[i - 1] + 1;
        }
        for(int i = nums.size() - 2;i >=0;i--){
            if(left[i] != 0) left[i] = max(left[i],left[i+1]);
        }
        // for(auto e: left) cout<<e<<' ';
        int ret = 0;
        for(int i = 1;i < size - 1;i++){
            if(nums[i] == 0)ret = max(ret,left[i - 1]+ left[i+1]);
        }
        if(ret == 0&& nums[1] == 1)  ret = nums.size() - 3;
        return ret;
    }
};
class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        vector<int> num(s.size());
        int size  = s.size();
        int left = 0,sum = 0,ret = 0;
        for(int right = 0;right < size;right++){
            sum += abs(s[right] - t[right]);
            num[right] =abs( s[right] - t[right]);
            while(sum > maxCost){ 
                sum -= num[left];
                left++;
            }
            ret = max(ret,right - left + 1);
            cout<< right - left + 1<<' ';
        }
        cout<<endl;
        for(auto e : num)   cout << e <<' ';
        return ret;
    }
};
class Solution {
public:
    int longestSemiRepetitiveSubstring(string s) {
        int old = 0,ret = min(1,(int)s.size()),size = s.size(),left = 0;
        for(int right = 1; right < size;right++){
            if(s[right] == s[right - 1])
            {
                ret = max(ret,right - left);
                if(old == 0) ret++;
                left = old;
                old = right;
            }else{
                ret = max(ret,right - left + 1);
            }
        }
        return ret;
    }
};
class Solution {
public:
    int maximumLengthSubstring(string s) {
        vector<int>num(26);
        int left = 0,ret = 0;
        for(int i = 0;i < s.size();i++){
            if(num[s[i] - 'a'] == 2)
            {
                while(s[left] != s[i]){
                    num[s[left] - 'a']--;
                     left++;
                }
                num[s[left] - 'a']--;
                left++;
            }
            num[s[i] - 'a']++;
            ret = max(ret,i - left + 1);
            // for(auto e : num) cout <<e;
            // cout<<endl;
        }

        return ret;
    }
};
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0,right = 0,ret = 0;
        unordered_map<int,int> mm;
        for(int right = 0; right <fruits.size();right++){
            mm[fruits[right]]++;
            while(mm.size() >2){
                mm[fruits[left]]--; if(mm[fruits[left]] == 0) mm.erase(fruits[left]);
                left++;
            }
            ret = max(ret,right - left + 1);
        }
        return ret;
    }
};
class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        int sum = 0,ret = 0, size = nums.size(),left = 0,right = 0;
        unordered_set<int> window;
        for( ; right < size;right++){
            if(window.count(nums[right]))
            {
                while(nums[left] != nums[right]){
                    sum -= nums[left];
                    window.erase(nums[left]);
                    left++;
                }
                sum -= nums[left];
                window.erase(nums[left]);
                left++;
            }
            window.insert(nums[right]);
            sum += nums[right];
            ret = max(sum,ret);
        }
        return ret;
    }
};
class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int sum = 0, ret = 0, size = nums.size(), left = 0, right = 0;
        unordered_map<int, int> window;
        for (; right < size; right++) {
            if (window[nums[right]] == k) {
                while (nums[left] != nums[right]) {
                    window[nums[left]]--;
                    left++;
                }
                window[nums[left]]--;
                left++;
            }
            window[nums[right]]++;
            ret = max(right - left + 1, ret);
        }
        return ret;
    }
};
int fun(string& an, int k,char ch){
    int node = 0, ret = 0, size = an.size(), left = 0, right = 0,sum = 0;
    for(;right <size;right++){
        if(an[right] == ch) node++;
        while(node > k){
            while(an[left] != ch)
                left++;
            left++;
            node--;
        }
        ret = max(ret,right - left + 1);
    }
    return ret;
}
class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        return max(fun(answerKey,k,'T'),fun(answerKey,k,'F'));
    }
};
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int node = 0, ret = 0, size = nums.size(), left = 0, right = 0, sum = 0;
        for (; right < size; right++) {
            if (nums[right] == 0)
                node++;
            if (node > k) {
                while (nums[left] != 0)
                    left++;
                left++;
                node--;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
    };
    class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int nowsum = 0, ret = 0, size = nums.size(), left = 0, right = 0, sum = 0;
        for(auto e : nums) sum += e;
        sum -= x;
        if(sum == 0) return size;
        for (; right < size; right++) {
            nowsum += nums[right];
            while(nowsum > sum){
                if(left >= size){
                    // if(ret == 0) return -1;
                    // return size - ret;
                    break;
                }
                nowsum -= nums[left];
                left++;
            }
            if(nowsum == sum){
                ret = max(ret, right - left + 1);
            }
        }
        if(ret == 0) return -1;
        return size - ret;
    }
};
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        int size =nums.size(),left = 0,right = 0,ret = 0;
        long long sum = 0;
        // vector<long long> vv(size);
        // vv[0] = nums[0];
        // for(int i = 1; i< size;i++) vv[i] = vv[i - 1] + nums[i];
        for(;right < size;right++){
            while(left <= right && (long long)k + sum < (long long)(right - left) * nums[right])
            {
                sum -= nums[left];
                left++;
            }
            sum += nums[right];
            ret = max(ret,right - left + 1);
        }
        return ret;
    }
};
int c_map[3];
void fun(string& s) {
    c_map[0] = 0, c_map[1] = 0, c_map[2] = 0;
    for (int i = 0; i < s.size(); i++) {
        c_map[s[i] - 'a']++;
    }
}
class Solution {
public:
    int takeCharacters(string s, int k) { 
        int size = s.size();
        fun(s);
        c_map[0]-=k,c_map[1]-=k,c_map[2]-=k; // 不能比这多了
        if(c_map[0] < 0 || c_map[1] < 0 || c_map[2] < 0)
            return  -1;
        int left = 0,right = 0,ret = 0;
        for(;right < size ;right++){
            int pos_r = s[right]-'a';
            c_map[pos_r]--;
            while(c_map[pos_r] < 0){
                c_map[s[left] - 'a']++;
                left++;
            }
            ret = max(ret,right - left + 1);
        } 
        return size - ret;
    }
};
class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        int size = nums.size();
        vector<vector<int> > vv (size + 1);
        for(int i = 0;i < size;i++){
            vv[nums[i]].push_back(i - vv[nums[i]].size());
        }
        int ret = 0;
        for(auto &e : vv){
            int left = 0;
            for(int right = 0;right < e.size();right++){
                while(e[right]- e[left] > k)
                    left++;
                ret = max(ret,right - left + 1);
            }
        }
        return ret;
    }
};
bool fun(vector<int>& v1, vector<int> v2) { return v1[0] > v2[0]; }
class Solution {
public:
    int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
        sort(tiles.begin(), tiles.end());
        int size = tiles.size(), left = 0, sum = 0, ret = 0;
        for (int right = 0; right < size; right++) {
            sum += tiles[right][1] - tiles[right][0] + 1;
            int mode = tiles[right][1] - carpetLen + 1;
            while (mode > tiles[left][1]) {
                sum -= tiles[left][1] - tiles[left][0] + 1;
                left++;
            }
            if (mode > tiles[left][0]) {
                sum -= mode - tiles[left][0];
                tiles[left][0] = mode;
            }
            ret = max(ret,sum);
        }
        return ret;
    }
};
class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        int n = prizePositions.size();
        int ans = 0,left = 0;
        vector<int>mx(n + 1);
        for(int right = 0;right < n;right++){
            while(prizePositions[right] - prizePositions[left] > k)
            {
                left++;
            }
            ans = max(ans,mx[left] + right - left + 1);
            mx[right + 1] = max(mx[right],right - left + 1);
            
            }
        return ans;
    }
};
class Solution {
public:
    int maxTotalFruits(vector<vector<int>> fruits, int startPos, int k) {
        int n = fruits.size(), ans = 0, sum = 0;
        unordered_map<int, int> mm;
        for (auto& ee : fruits) {
            mm[ee[0]] = ee[1];
        }

        int left = max(0, startPos - k - 1);
        for (int right = left; startPos + k > right; right++) {
            if (left <startPos && right > startPos) {
                if (mm.contains(left) )
                    sum -= mm[left];
                if (left + 1 < startPos && mm.contains(left + 1))
                    sum -= mm[left+ 1];
                left += 2;
                left = min(left, startPos);
            }
            if (mm.contains(right))
                sum += mm[right];
            ans = max(ans, sum);
        }
        return ans;
    }
};
class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        int n = fruits.size(), ans = 0, sum = 0;
        if(n == 1 && fruits[0][0] + k >= startPos && startPos + k >= fruits[0][0])
            return fruits[0][1]; 
        map<int, int> mm;
        for (auto& e : fruits) {
            mm[e[0]] = e[1];
        }
        int left = max(0, startPos - k);
        for (int pos = left; pos < startPos; pos++)
            if (mm.contains(pos))
                sum += mm[pos];
        for (int right = startPos; right <= startPos + k; right++) {
            while (right - left + min(right - startPos, startPos - left) > k) {
                if(mm.contains(left))
                    sum -= mm[left];
                left++;
            }
            if(mm.contains(right))
                sum += mm[right];
            ans = max(ans,sum);
        }
        return ans;
    }
};
class Solution {
public:
    int minOperations(vector<int> &nums) {
        ranges::sort(nums);
        int n = nums.size();
        int m = unique(nums.begin(), nums.end()) - nums.begin(); // 原地去重
        // for(auto e : nums) cout << e <<endl;
        int ans = 0, left = 0;
        for(int i = 0;i < m;i++){
            while(nums[left] + n - 1< nums[i])
                left++;
            ans = max(ans,i - left + 1);
        }
        return n - ans;
    }
};
class Solution {
public:
    int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
        vector<double> vv;
        int ans1 = 0;
        int posx = location[0],posy = location[1];
        for(auto &e : points){
            if(e[1] == posy && e[0] == posx) {
                ans1++;continue;
            }
            double degree = atan2(e[1] - posy,e[0] - posx);
            vv.push_back(degree);
        }
        sort(vv.begin(),vv.end());
        int m = vv.size(),ans2 = 0;
        for(int i = 0;i < m;i++) vv.push_back(vv[i] + 2*M_PI);
        double len = angle * M_PI / 180;
        int right = 0;
        for(int left = 0; left < m;left++){
            while(vv[right] <= vv[left] + len)
                ans2 = max(ans2,right - left + 1),right++;
        }
        return ans1 + ans2;
    }
};
class Solution {
public:
    int visiblePoints(vector<vector<int>>& points, int angle,
                      vector<int>& location) {
        int n = points.size(), right = 0, somepos = 0, findpos = 0;
        double len = angle * M_PI / 180;
        vector<double> vv;
        for (int i = 0; i < n; i++) {
            if (points[i][1] == location[1] && points[i][0] == location[0]) {
                somepos++;
                continue;
            }
            vv.emplace_back(
                atan2(points[i][1] - location[1], points[i][0] - location[0]));
        }
        int m = vv.size();
        cout << m << endl;
        sort(vv.begin(), vv.end());
        for (int i = 0; i < m; i++)
            vv.emplace_back(vv[i] + 2 * M_PI);

        for (int left = 0; left < m; left++) {
            while (vv[right] <= vv[left] + len) {
                // findpos = max(findpos, right - left + 1), right++;
                right++,findpos = max(findpos,right - left);
            }
        }
        return findpos + somepos;
    }
};
class Solution {
public:
    int longestValidSubstring(string word, vector<string>& forbidden) {
        int n = word.size(), ret = 0;
        unordered_set fb(forbidden.begin(), forbidden.end());
        int left = 0;
        for (int right = 0; right < n; right++) {
            for (int i = right; i >= left && i > right - 10; i--) {
                if (fb.count(word.substr(i, right - i + 1))) {
                    left = i + 1;
                    break;
                }
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};
long long fun(vector<int>& nums,vector<long long>&sum_node,int left,int right)
{
    int mid = (right + left) / 2;   // 中位数
    long long left_data = (long long)(mid - left)*nums[mid] - (sum_node[mid] - sum_node[left]);
    long long right_data = (long long)(sum_node[right + 1] - sum_node[mid + 1]) - (long long)(right - mid)*nums[mid];
    // cout << left <<' '<< right << ' '<<left_data + right_data<<endl;
    return left_data + right_data;
}
class Solution {
public:
    int maxFrequencyScore(vector<int>& nums, long long k) {
        int n = nums.size(),ans = 0;
        sort(nums.begin(),nums.end());

        vector<long long> sum_node(n + 1);
        sum_node[0] = 0;
        for(int i = 1;i <= n;i++)
            sum_node[i] = sum_node[i - 1] + nums[i - 1];

        int left = 0;
        for(int right = 0;right < n; ++right)
        {
            while(fun(nums,sum_node,left,right) > k){
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        sort(stones.begin(),stones.end());
        int n = stones.size();
        
        int e1 = stones[n - 1] - stones[1] - n + 2;
        int e2 = stones[n - 2] - stones[0] - n + 2;

        int ans2 = max(e1,e2);
        if(e1 == 0 || e2 == 0){   // 左右有一侧都黏在一堆
            return {min(2,ans2),ans2};
        }
        int ans1 = 100000000;
        int left = 0;
        for(int right = 0;right < n;right++){
            while(stones[left] + n < stones[right])
                left++;
            ans1 = min(ans1,n - (right - left + 1));
        }
        return {ans1,ans2};
    }
};
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size();
        if(k > n) return 0;
        if(k == 1) return n;
        vector<int> num(26);
        for(int i = 0;i < n;i++){
            num[s[i] - 'a']++;
        }
        for(int i = 0;i < n;i++){
            if(num[s[i] - 'a'] > 0 && num[s[i] - 'a'] < k){
                int t1 = longestSubstring(s.substr(0,i),k);
                int t2 = longestSubstring(s.substr(i+1),k);
                return max(t1,t2);
            }
        }
        return n;
    }
};
char fun(char c) {
    if (c >= 'a' && c <= 'z')
        return c - 'a' + 'A';
    return c - 'A' + 'a';
}
class Solution {
public:
    string longestNiceSubstring(string s) {
        int n = s.size(), ans1 = 0, ans2 = 0;

        for (int t = 1; t <= 26; t++) // t 代表字串不重复的元素数量
        {
            vector<int> num(256);
            int left = 0, right = 0, char_num = 0, err_num = 0;
            for (; right < n; right++) {
                // int t = 2;
                num[s[right]]++;
                if (num[s[right]] == 1 && num[fun(s[right])] == 0) {
                    char_num++, err_num++;
                }
                if (num[s[right]] == 1 && num[fun(s[right])] != 0) {
                    err_num--;
                }

                while (t < char_num) {
                    num[s[left]]--;
                    if (num[s[left]] == 0 && num[fun(s[left])] == 0) {
                        char_num--, err_num--;
                    }
                    if (num[s[left]] == 0 && num[fun(s[left])] != 0) {
                        err_num++;
                    }
                    left++;
                }
                if (err_num == 0) {
                    if (right - left + 1 > ans2) {
                        ans1 = left;
                        ans2 = max(ans2, right - left + 1);
                    }
                    cout << s.substr(ans1, ans2) << endl;
                }
            }
        }
        return s.substr(ans1, ans2);
    }
};
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = 1000000000,left = 0,sum = 0;
        for(int right = 0;right < n;right++){
            sum += nums[right];
            while(sum >= target){
                ans = min(ans, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        if(ans == 1000000000) return 0;
        return ans;
        
    }
};
class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int n = s.size(), ans1 = 0, ans2 = 1000000, left = 0;
        string ans(1000,'1');
        for (int right = 0; right < n; right++) {
            if (s[right] == '1')
                k--;
            while (k == 0) {
                string tmp = s.substr(left, right - left + 1);

                if (right - left + 1 < ans.size()) {
                    ans = tmp;
                }else if(right - left + 1 == ans.size()){
                    ans = min(ans,tmp);
                }
                if (s[left] == '1')
                    k++;
                left++;
            }
        }
        if (ans == string(1000,'1'))
            return "";
        return ans;
    }
};